Theo truyền thống, phần mềm máy tính được viết cho tính toán tuần tự. Để giải quyết một vấn đề, một thuật toán được xây dựng và thực thi tuần tự theo các dòng lệnh. Những câu lệnh này lại được chạy trên một đơn vị xử lý trung tâm (CPU) của chiếc máy tính. Chỉ có một câu lệnh được chạy trong một khoảng thời gian. Sau khi câu lệnh đó kết thúc, câu tiếp theo mới được thực hiện.[6]

Tính toán song song, mặt khác, lại sử dụng đồng thời các bộ đa xử lý để giải quyết một vấn đề. Việc này được hoàn thành bằng cách tách vấn đề thành nhiều phần độc lập sau đó mỗi bộ xử lý có thể chạy thuật toán của nó đồng thời với những cái khác. Các bộ phận xử lý có thể khác nhau và bao gồm các dạng tài nguyên như: một máy tính đơn gồm nhiều bộ đa xử lý, nhiều máy tính được kết nối mạng, phần cứng chuyên biệt, hoặc có thể là sự kết hợp của những dạng trên.[6]

Tăng tần số là cách chủ đạo để cải thiện khả năng xử lý của máy tính từ giữa những năm 1980 cho đến năm 2004. Thời gian chạy của một chương trình được tính bằng số câu lệnh nhân với thời gian trung bình của một câu lệnh. Như vậy nếu duy trì tất cả những thứ khác ổn định, gia tăng tần số xung nhịp sẽ làm giảm thời gian trung bình để thực thi một câu lệnh. Như vậy tần số tăng sẽ giảm đi thời gian chạy của những chương trình chạy trong CPU.[7]

Tuy nhiên, mức tiêu hao năng lượng của một con chip được tính bởi công thức P = C × V2 × F, trong đó P là công suất tiêu thụ, C là điện dung được chuyển trong mỗi chu kỳ xung nhịp (tỷ lệ thuận với số lượng transistor có đầu vào thay đổi), V là điện áp, và F là tần số của bộ xử lý (số chu kỳ mỗi giây).[8] Như vậy tăng tần số cũng làm năng lượng sử dụng của bộ xử lý tăng theo. Việc tăng tiêu hao năng lượng này đã dẫn đến quyết định ngừng phát triển bộ xử lý Tejas và Jayhawk của Intel tháng 5 năm 2004, được cho là sự chấm dứt của việc sử dụng tăng tần số như một kiến trúc máy tính chủ đạo.[9]

Định luật Moore là một quan sát thực tế cho thấy mật độ transistor trong bộ vi xử lý tăng gấp hai lần sau mỗi 18 đến 24 tháng.[10] Bất chấp nhược điểm về tiêu hao năng lượng, và những dự đoán về sự chấm dứt của nó, định luật Moore vẫn khá thông dụng. Với sự kết thúc của phương pháp tăng tần số, các transistor bổ sung này (không còn được sử dụng cho việc tăng tần số) có thể được sử dụng để tạo ra phần cứng bổ sung cho tính toán song song.

Định luật Amdahl và định luật Gustafson

Biểu diễn định luật Amdahl. Khả năng tăng tốc của một chương trình song song hóa bị hạn chế bởi việc có bao nhiêu phần của chương trình có thể được song song. Ví dụ, nếu 90% chương trình được song song, tốc độ tăng cực đại khi sử dụng tính toán song song sẽ là gấp 10 lần, không phụ thuộc vào bao nhiêu bộ xử lý được sử dụng.

Trong trường hợp tối ưu, khả năng tăng tốc từ việc song song hóa là tuyến tính — gấp đôi các thành phần xử lý sẽ làm giảm một nửa thời gian chạy, và gấp đôi lần nữa sẽ lại tiếp tục giảm thời gian chạy xuống còn một nửa. Tuy nhiên, có rất ít thuật toán song song có thể đạt được sự tăng tốc tối ưu. Hầu hết đều chỉ đạt đến gần mức tuyến tính khi số thành phần xử lý là nhỏ, và tiệm cận đến một giá trị không đổi khi số lượng các thành phần xử lý tăng lên nhiều.

Tiềm năng của việc tăng tốc bởi một thuật toán trên nền tảng tính toán song song được đưa ra bởi định luật Amdahl, ban đầu được xây dựng bởi Gene Amdahl trong những năm 1960.[11] Trong đó nói rõ rằng chỉ một phần nhỏ của chương trình không thể được song song cũng sẽ hạn chế khả năng tăng tốc tổng thể của việc song song hóa. Một chương trình giải quyết một vấn đề toán học hoặc kỹ thuật lớn thường sẽ bao gồm một số bộ phận song song và bộ phận không song song (tuần tự). Nếu α {\displaystyle \alpha } là tỷ lệ thời gian chạy mà một chương trình tuần tự bỏ ra trên bộ phận không song song, thì

S = 1 α {\displaystyle S={\frac {1}{\alpha }}}

là tỷ lệ tăng tốc tối đa khi song song hóa chương trình. Ví dụ, nếu coi phần tuần tự của một chương trình là 10% thời gian chạy, tốc độ tăng sẽ không thể đạt được quá 10 lần, bất kể có bao nhiêu bộ xử lý được thêm vào. Điều này đặt ra một giới hạn về tính hữu ích của việc thêm các đơn vị thực hiện song song với nhau nhiều hơn. "Khi công việc không thể được phân chia vì ràng buộc về trình tự, dù có áp dụng thêm nhiều phương pháp cũng không ảnh hưởng đến tiến độ. Mang thai một đứa trẻ phải mất 9 tháng, cho dù có bao nhiêu người phụ nữ đi nữa."[12]

Giả sử một công việc có hai bộ phận độc lập, A và B. B chiếm khoảng 25% thời gian của toàn bộ tính toán. Với nỗ lực, một lập trình viên có thể làm cho phần việc này nhanh gấp 5 lần, nhưng điều này chỉ làm giảm thời gian của toàn bộ tính toán đi một chút. Ngược lại, người đó có thể chỉ phải làm việc ít hơn để khiến cho phần A nhanh gấp hai lần. Phương án thứ hai sẽ làm cho toàn bộ công việc tiến triển nhanh hơn so với phương án thứ nhất, mặc dù B có tốc độ tăng lớn hơn (5× so với 2×).

Định luật Gustafson là một nguyên lý khác trong tính toán, liên quan chặt chẽ đến định luật Amdahl.[13] Nó chỉ ra rằng việc tăng tốc với P {\displaystyle P} bộ xử lý là

S ( P ) = P − α ( P − 1 ) . {\displaystyle S(P)=P-\alpha (P-1).\,}

Định luật Amdahl giả định kích thước bài toán là cố định và thời gian chạy của các phần tuần tự của chương trình là độc lập với số lượng bộ xử lý, trong khi định luật Gustafson không đưa ra giả thuyết này.

Phụ thuộc

Hiểu biết về phụ thuộc dữ liệu là bước cơ bản trong việc thực hiện thuật toán song song. Không một chương trình nào có thể chạy nhanh hơn chuỗi dài nhất của các phép tính phụ thuộc (được biết đến như là đường tới hạn), khi mà các phép tính phụ thuộc vào các phép tính trước trong chuỗi phải được thực hiện theo thứ tự. Tuy nhiên, hầu hết các thuật toán không chỉ bao gồm một chuỗi dài các phép tính phụ thuộc, luôn luôn có khả năng phải thực hiện các phép tính độc lập song song.

Cho Pi và Pj là hai đoạn của chương trình. Bernstein's conditions[14] mô tả khi nào hai đoạn độc lập với nhau và có thể được thực hiện song song. Với Pi, đặt Ii là tất cả các biến đầu vào, Oi là biến đầu ra, tương tự ta làm như vậy với Pj. P i và Pj là độc lập nếu chúng thỏa mãn

• I j ∩ O i = ∅ , {\displaystyle I_{j}\cap O_{i}=\varnothing ,\,}
• I i ∩ O j = ∅ , {\displaystyle I_{i}\cap O_{j}=\varnothing ,\,}
• O i ∩ O j = ∅ . {\displaystyle O_{i}\cap O_{j}=\varnothing .\,}

Không thỏa mãn điều kiện đầu tiên sẽ tạo ra một phụ thuộc lưu lượng, giông như câu lệnh đầu tiên sẽ tạo ra một kết quả được sử dụng ở câu lệnh thứ hai. Điều kiện thứ hai có thể coi là chống phụ thuộc, khi mà câu lệnh thứ hai (Pj) sẽ ghi đè lên biến được sử dụng ở biểu thức thứ nhất (Pi). Điều kiện thứ ba và cuối cùng thể hiện một sự phụ thuộc đầu ra: Khi hai câu lệnh cùng thực hiện một công việc, kết quả cuối cùng phải lấy từ các câu lệnh thực hiện một cách hợp lý nhất.[15]

Xem xét các hàm sau đây, trong đó thể hiện nhiều loại phụ thuộc:

1: function Dep(a, b)2: c:= a•b3: d:= 2•c4: end function

Operation 3 in Dep(a, b) cannot be executed before (or even in parallel with) operation 2, because operation 3 uses a result from operation 2. It violates condition 1, and thus introduces a flow dependency.

1: function NoDep(a, b)2: c:= a•b3: d:= 2•b4: e:= a+b5: end function

Trong ví dụ này, không có phụ thuộc giữa các chỉ lệnh, do đó, tất cả đều có thể chạy song song.

Điều kiện của Bernstein không cho phép bộ nhớ được chia sẻ giữa các quá trình khác nhau. Nó cho rằng, một số phương tiện thực thi một lệnh giữa các truy cập là cần thiết, ví dụ như semaphores, barriers hoặc một số phương pháp đồng bộ khác.

Race conditions, mutual exclusion, synchronization, và parallel slowdown

Công việc phụ trong một chương trình song song thường được gọi là threads. Một số kiến trúc máy tính song song sử dụng các phiên bản nhỏ và nhẹ hơn gọi là fibers, trong khi các phiên bản lớn được gọi là processes. Tuy nhiên, "threads" thường được chấp nhận như một thuật ngữ chung cho các công việc phụ. Threads sẽ phải thường xuyên cập nhật các biến được chia sẻ giữa chúng. Các chỉ lệnh giữa hai chương trình có thể được xen kẽ theo bất kỳ thứ tự nào. Ví dụ, xem chương trình sau đây:

Thread A	Thread B
1A: Read variable V	1B: Read variable V
2A: Add 1 to variable V	2B: Add 1 to variable V
3A Write back to variable V	3B: Write back to variable V

Nếu chỉ lệnh 1B được thực hiện giữa 1A và 3A, hoặc nếu chỉ lệnh được thực hiện giữa 1B và 3B, chương trình sẽ tạo ra dữ liệu không chính xác. Đây được gọi là một race condition. Chương trình sẽ phải sử dụng khóa để cung cấp mutual exclusion. Khóa là một cấu trúc ngôn ngữ lập trình cho phép một thread kiểm soát một biến và ngăn ngừa các biến khác đọc hoặc ghi nó, cho đến khi biến đó được mở khóa. Thread giữ khóa có thể hoàn toàn thoải mái truy cập phần tới hạn của nó (phần của chương trình yêu cầu quyền truy cập chuyên biệt tới một số biến), và mở khóa các dữ liệu khi nó được hoàn tất. Vì vậy, để đảm bảo chương trình thực hiện chính xác, chương trình trên có thể được viết lại để sử dụng khóa:

Thread A	Thread B
1A: Lock variable V	1B: Lock variable V
2A: Read variable V	2B: Read variable V
3A: Add 1 to variable V	3B: Add 1 to variable V
4A Write back to variable V	4B: Write back to variable V
5A: Unlock variable V	5B: Unlock variable V

Một thread sẽ khóa biến V thành công, trong khi các thread khác sẽ bị khóa lại—không thể truy cập cho đến khi V được mở khóa. Điều này đảm bảo chương trình được thực hiện đúng. Để đảm bảo chương trình thực hiện chính xác, khóa rất có thể sẽ làm chậm chương trình khi cần thiết.

Khóa nhiều biến bằng cách sử dụng phương pháp khóa non-atomic có khả năng tạo ra một deadlock. Một khóa atomic khóa nhiều biến cùng một lúc. Nếu nó không thể khóa một trong số các biến đó, nó sẽ không khóa biến nào. Nếu hai thread cùng khóa hai biến giống nhau bằng khóa non-atomic, có khả năng một thread sẽ khóa một biến và thread thứ hai sẽ khóa biến còn lại. Trong trường hợp này, không thread nào có thể hoàn tất, và kết quả là deadlock.

Nhiều chương trình song song yêu cầu các công việc phụ act in synchrony (thực hiện đồng bộ). Điều này đòi hỏi việc sử dụng một barrier (hàng rào). Những barrier thường được tạo ra bằng cách sử dụng khóa phần mềm. Một lớp của thuật toán, được gọi là lock-free and wait-free algorithms, hoàn toàn có thể tránh được việc sử dụng khóa và barrier. Tuy nhiên, cách tiếp cận này thường khó thực hiện và yêu cầu thiết kế cấu trúc dữ liệu một cách chính xác.

Không phải tất cả mọi song song hóa đều cho kết quả tăng tốc độ. Nói chung, khi một công việc được chia ra thành càng nhiều thread, thì thời gian những thread đó sử dụng để kết nối với nhau sẽ ngày càng tăng. Suy cho cùng, tổng chi phí từ việc kết nối vượt trội thời gian sử dụng để giải quyết vấn đề, và song song hóa hơn nữa (nghĩa là, tách khối lượng công việc thành nhiều thread hơn) sẽ là tăng hơn là giảm thời gian cần thiết để hoàn thành. Đây được gọi là parallel slowdown.

Fine-grained, coarse-grained, và embarrassing parallelism

Các ứng dụng thường được phân loại theo mức độ thường xuyên của các công việc phụ của họ cần phải đồng bộ hóa hoặc giao tiếp với nhau. Một ứng dụng được cho là song song hạt mịn nếu các công việc phụ của nó giao tiếp nhiều lần mỗi giây; gọi là song song hạt thô nếu chúng kết nối nhiều lần mỗi giây, và là embarrassingly parallel nếu rất ít hoặc không bao giờ kết nối. Các ứng dụng embarrassingly parallel được xem là dễ song song nhất.

Mô hình thống nhất

Ngôn ngữ lập trình song song và các máy tính song song phải có một mô hình thống nhất (còn được gọi là một mô hình bộ nhớ). Các mô hình thống nhất xác định các quy tắc về cách hoạt động trên bộ nhớ máy tính xảy ra và làm thế nào tạo ra kết quả.

Một trong những mô hình thống nhất đầu tiên là mô hình tuần tự thống nhất của Leslie Lamport. Tuần tự thống nhất là một tính chất của một chương trình song song khi thực hiện song song của nó tạo ra kết quả tương tự như một chương trình tuần tự. Cụ thể, một chương trình là tuần tự thống nhất nếu "... kết quả của bất kỳ hành động nào đều giống như là các hành động của tất cả các bộ xử lý được thực hiện theo một quy tắc tuần tự, và các hoạt động của mỗi bộ xử lý cá nhân xuất hiện trong trình tự này theo một thứ tự xác định bởi chương trình".[16]

Bộ nhớ giao tác phần mềm là một dạng phổ biến của mô hình thống nhất. Bộ nhớ giao tác phần mềm vay mượn từ lý thuyết cơ sở dữ liệu khái niệm của giao dịch nguyên tử và áp dụng chúng để truy cập bộ nhớ.

Dưới góc độ toán học, các mô hình này có thể được thể hiện bằng nhiều cách. Mạng Petri, được giới thiệu trong luận án tiến sĩ của Carl Adam Petri năm 1962, là một cố gắng sớm để hệ thống hóa các quy tắc của mô hình thống nhất. Lý thuyết luồng dữ liệu sau này xây dựng dựa trên những, và kiến trúc luồng dữ liệu được tạo ra để thực hiện những ý tưởng của lý thuyết luồng dữ liệu. Bắt đầu từ cuối những năm 1970, process calculi như Phép tính của hệ thống truyền thông và Quá trình giao tiếp tuần tự đã được phát triển để cho phép đại số lý luận về hệ thống gồm các thành phần tương tác. Những bổ sung gần đây cho quá trình tính toán, ví dụ như phép tính π, đã thêm vào các khả năng cho lý luận về cấu trúc liên kết năng động. Những logic như TLA+ của Lamport, và các mô hình toán học như là dấu vết và biểu đồ sự kiện tác động, cũng đã được phát triển để mô tả hành vi của hệ thống tương tranh.

Phân loại Flynn

Michael J. Flynn đã tạo ra một trong những hệ thống phân loại sớm nhất cho các máy tính và chương trình song song (và tuần tự), bây giờ được gọi là Phép phân loại của Flynn. Flynn phân loại chương trình và máy tính bằng cách chúng có thể đã được điều hành bằng cách sử dụng một hay nhiều bộ chỉ lệnh, những chỉ lệnh đó có thể có hoặc không sử dụng một hay nhiều bộ dữ liệu.

Bản mẫu:Phân loại Flynn

Kiểu phân loại single-instruction-single-data (SISD) tương đương với một chương trình hoàn toàn tuần tự. Kiểu phân loại single-instruction-multiple-data (SIMD) tương tự như thực hiện các hoạt động liên tục trên cùng một tập dữ liệu lớn. Kiểu này thường được dùng trong các ứng dụng xử lý tín hiệu. Multiple-instruction-single-data (MISD) là một kiểu phân loại hiếm khi được sử dụng. Trong khi các kiến trúc máy tính để xử lý vấn đề này được nghĩ ra (ví dụ như mảng tâm thu), vài ứng dụng phù hợp được hiện thực hóa. Các chương trình multiple-instruction-multiple-data (MIMD) đang là dạng phổ biến nhất trong các chương trình song song.

Theo David A. Patterson và John L. Hennessy, "Một số cỗ máy là sự kết hợp của những loại này, nhưng mô hình cổ điển này đã tồn tại bởi tính đơn giản, dễ hiểu, và đưa ra được xấp xỉ đầu tiên với kết quả tốt. Nó cũng là chương trình được sử dụng rộng rãi nhất-có lẽ vì tính dễ hiểu của mình."[17]